package com.atues.backtrack.partiation;



import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * @author: liang
 * @time: 2025-02-13 21:16
 */
class Solution {
    List<List<String>> res = new ArrayList<List<String>>();
    List<String> path = new ArrayList<>();
    public List<List<String>> partition(String s) {
        backtracking(s,0);
        return  res;
    }


    public void backtracking(String s,  int start){
        if(start == s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = start; i < s.length(); i ++){
            if(isPart(s.substring(start,i+1))){
                path.add(s.substring(start,i+1));
                backtracking(s,i+1);
                path.remove(path.size() - 1);
            }
        }
    }

    public boolean isPart(String s){
        int l = 0 ;
        int r = s.length() - 1;
        while(l < r){
            if( s.charAt(l) != s.charAt(r))return false;
            l++;
            r--;
        }
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();


        System.out.println(JSON.toJSONString( solution.partition("aab")));
    }
}